/**
 * реализации алгоритмов
 */
import java.io.*;
import java.util.*;

class GraphsUtils {
	/**
	 * прочитать граф из файла, в котором лежит описание цепей
	 * в первой строке должно быть число вершин, в остальных - номера вершин, входящих в цепь
	 */
	public static Graph readGraphByBranches (String filepath){
		try {
			BufferedReader br = new BufferedReader (new FileReader (filepath));
			int n = Integer.parseInt (br.readLine ());
			Graph g = new Graph (n);
			while (br.ready ()) {
				// split
				String arr[] = br.readLine ().split (" ");
				// unique
				TreeSet s = new TreeSet ();
				for (String elem : arr) {
					s.add (Integer.parseInt (elem));
				}
				int arr_unique[] = new int[s.size ()];
				for (int j = 0; s.size () > 0; ++ j) {
					arr_unique[j] = ((Integer)s.first ()).intValue ();
					s.remove (s.first ());
				}
				// edges
				for (int u = 0; u < arr_unique.length; ++ u)
					for (int v = 0; v < arr_unique.length; ++ v)
						if (u < v)
							g.addEdge (arr_unique[u] - 1, arr_unique[v] - 1, 1);
			}
			br.close ();
			return g;
		}
		catch (Exception e){
			System.out.println ("Error in read graph: " + e);
		}
		return null;
	}
	/**
	 * прочитать граф из файла, в котором лежит матрица R
	 * в первой строке должно быть число вершин
	 */
	public static Graph readGraphByR (String filepath){
		try {
			BufferedReader br = new BufferedReader (new FileReader (filepath));
			int n = Integer.parseInt (br.readLine ());
			Graph g = new Graph (n);
			for (int i = 0; i < g.count (); ++ i) {
				String r[] = br.readLine ().split (" ");
				for (int j = 0; j < g.count (); ++ j)
					g.setEdge (i, j, Integer.parseInt (r[j]));
			}
			br.close ();
			return g;
		}
		catch (Exception e){
			System.out.println ("Error in read graph: " + e);
		}
		return null;
	}
	/**
	 * обход графа в глубину в поисках Эйлерова цикла
	 * @param v - вершина с которой начать обход
	 * @param R - матрица R
	 * @param n - количество вершин
	 * @param vertices - эйлеров цикл
	 */
	public static void eulerCycleDfs (int v, int [][]R, int n, ArrayList vertices){
		for (int u = 0; u < n; ++ u)
			if (R[v][u] > 0){
				-- R[v][u];
				-- R[u][v];
				eulerCycleDfs (u, R, n, vertices);
			}
		vertices.add (v);
	}
	/**
	 * найти в графе эйлеров цикл
	 */
	public static ArrayList eulerCycle (Graph g){
		int n = g.count ();
		if (n == 1){
			ArrayList result = new ArrayList ();
			result.add (0);
			return result;
		}
		if (n < 1)
			return null;
		int first = - 1;
		int last = - 1;
		for (int i = 0; i < n; ++ i)
			if (g.degree (i) % 2 == 1)
				if (first == - 1)
					first = i;
				else
					if (last == - 1)
						last = i;
					else
						return null;
		if (first == - 1){
			first = 0;
			last = 1;
		}
		
		int [][]R = new int[n][n];
		for (int i = 0; i < n; ++ i)
			for (int j = 0; j < n; ++ j)
				R[i][j] = g.getEdge (i, j);
		ArrayList vertices = new ArrayList ();
		eulerCycleDfs (first, R, n, vertices);

		return vertices;
	}
	/**
	 * найти в графе максимальную клику
	 */
	public static ArrayList findMaxFullGraph (Graph g) {
		int n = g.count ();
		for (int p = (1 << (n - 1)) - 1; p >= 1; -- p){
			boolean flagNo = false;
			for (int i = 0; i < n; ++ i)
				for (int j = 0; j < n; ++ j)
					if (i != j && g.getEdge (i, j) == 0 && (((p >> i) & 1) == 1) && (((p >> j) & 1) == 1))
						flagNo = true;
			if (! flagNo){
				ArrayList vertices = new ArrayList ();
				for (int i = 0; i < n; ++ i)
					if (((p >> i) & 1) == 1)
						vertices.add (i);
				return vertices;
			}
		}
		return null;
	}
	/**
	 * поиск числа Хадвигера
	 */
	public static HadvigersResult findHadvigersNumbersEdges (Graph g){
		int c = 1000; // чем больше, тем лучше/дольше мы будем искать
		int n = g.count ();
		int m = g.countEdges ();

		Random r = new Random ();
		int v, u;
		for (int k = 1; k < m; ++ k) {
			for (int ic = 0; ic < c; ++ ic) {
				HadvigersResult hr = new HadvigersResult ();
				hr.g = g.clone ();
				for (int i = 0; i < k; ++ i) {
					do {
						v = r.nextInt (hr.g.count ());
						u = r.nextInt (hr.g.count ());
					}
					while (hr.g.getEdge (v, u) == 0);
					hr.addPairVertecs (v, u);
					hr.g.couple (v, u);
					hr.g_hist.add (hr.g.clone ());
					if (hr.g.isFull ())
						return hr;
				}
			}
		}
		return null;
	}
}